package NiuKe;

import java.util.HashMap;

/**
 * 段誉身具凌波微波，动无常则，若危若安，一次能走一级台阶或者两级台阶，
 * 他要爬一段30级的山路，问有多少种走法？分析如何计算，然后编程解答。
 * 进阶问题：当他轻功熟练度提升，一次最多可以走三级，那就结果有什么变化？
 * 后来走火入魔了，不能走一级，只能走二或三级，又有什么变化？
 */
public class PaLouTiPlus {
    public static void main(String[] args) {
        solution(30);
    }
    public static void solution(int n){
        int first = first(n);
        int second = second(n);
        int third = third(n);
        System.out.println(first + " " + second + " " + third);
    }
    // 爬1，2
    public static int first(int n){
        if(n == 1){
            return 1;
        }
        if(n == 2){
            return 2;
        }
        int[] dp = new int[2];
        dp[0] = 1;
        dp[1] = 2;
        for(int i = 2;i < n;i++){
            int result = dp[0] + dp[1];
            dp[0] = dp[1];
            dp[1] = result;
        }
        return dp[1];
    }
    // 爬1,2,3
    public static int second(int n){
        if(n == 1){
            return 1;
        }
        if(n == 2){
            return 2;
        }
        if(n == 3){
            return 4;
        }
        int[] dp = new int[3];
        dp[0] = 1;
        dp[1] = 2;
        dp[2] = 4;
        for(int i = 3;i < n;i++){
            int result = dp[0] + dp[1] + dp[2];
            dp[0] = dp[1];
            dp[1] = dp[2];
            dp[2] = result;
        }
        return dp[2];
    }
    // 爬2,3
    public static int third(int n){
        if(n == 1){
            return 0;
        }
        if(n == 2){
            return 1;
        }
        if(n == 3){
            return 1;
        }
        int[] dp = new int[3];
        dp[0] = 0;
        dp[1] = 1;
        dp[2] = 1;
        for(int i = 3;i < n;i++){
            int result = dp[0] + dp[1];
            dp[0] = dp[1];
            dp[1] = dp[2];
            dp[2] = result;
        }
        return dp[2];
    }
}
